package com.zhanghp.class01.sort;

import static com.zhanghp.class01.sort.utils.SortUtils.*;

/**
 * 选择排序
 *
 * @author zhanghp
 * @date 2023/7/26 16:39
 */
public class SelectionSort {
    public static void main(String[] args) {
        int[] arr = rand(10);
        printArr(arr);
        sort(arr);
        printArr(arr);
    }

    /**
     * 选择排序
     * 数值排序：小 -> 大
     *
     * @param arr 乱序数组
     */
    public static void sort(int[] arr) {
        // 边界条件
        if (arr == null || arr.length < BOUNDERY_LENGTH) {
            return;
        }
        // 被比较的固定索引
        for (int i = 0; i < arr.length; i++) {
            int minValueNum = i;
            // 固定索引与多个索引比较，选出最小更新在固定索引位置上
            for (int j = minValueNum + 1; j < arr.length; j++) {
                int num = arr[minValueNum] > arr[j] ? j : minValueNum;
                swap(arr, minValueNum, num);
            }
        }
    }

    /**
     * 选择排序2 - 优化：减少无用swap次数
     * 数值排序：小 -> 大
     *
     * @param arr 乱序数组
     */
    public static void sort2(int[] arr) {
        // 边界条件
        if (arr == null || arr.length < BOUNDERY_LENGTH) {
            return;
        }
        // 被比较的固定索引
        for (int i = 0; i < arr.length; i++) {
            // 固定索引与多个索引比较，选出最小更新在固定索引位置上
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] < arr[j]) {
                    continue;
                }
                swap(arr, i, j);
            }
        }
    }

}
